package com.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Lxk on 2019/6/1.
 */
public class Solution842 {

    List<Integer> realRes = new ArrayList<>();

    private boolean flag;

    private Integer str2Int(char[] chs,int begin,int length){
        int res = 0;
        for(int i = begin; i< begin + length; i++){
            res *= 10;
            res += (chs[i]-'0');
        }
        return res;
    }

    private boolean checkRemain(char[] chs,int begin,List<Integer> res){
        int prePre = res.get(0);
        int pre = res.get(1);

        for(int i = begin; i < chs.length ;){
            int temp = pre + prePre;
            String str = String.valueOf(temp);
            StringBuffer sb = new StringBuffer();
            for(int k = i; k<i+str.length()&&k<chs.length; k++){
                sb.append(chs[k]);
            }
            if(!str.equals(sb.toString())){
                return false;
            }else{
                i = i+str.length();
                prePre = pre;
                pre = temp;
            }
        }
        flag = false;
        return true;
    }

    private void recursive(char[] chs,int begin,int num,List<Integer> res){
        if(num==2){
            if(checkRemain(chs,begin,res)&&flag){
                int prePre = res.get(0);
                realRes.add(prePre);
                int pre = res.get(1);
                realRes.add(pre);

                for(int i = begin; i < chs.length ;){
                    int temp = pre + prePre;
                    String str = String.valueOf(temp);
                    StringBuffer sb = new StringBuffer();
                    for(int k = i; k<i+str.length(); k++){
                        sb.append(chs[k]);
                    }
                    i = i+str.length();
                    prePre = pre;
                    pre = temp;
                    realRes.add(pre);
                }
            }
            return ;
        }
        int arrLen = 0;
        if(num==0){
            arrLen = begin-1+(chs.length-begin)/2;
        }else{
            arrLen = begin-1+(chs.length-begin)/(3-num);
        }
        for(int i = begin;i <= arrLen; i++){
            int len = i+1-begin;
            Integer addNum = str2Int(chs,begin,len);
            res.add(addNum);
            recursive(chs,begin + len,num+1,res);
            res.remove(addNum);
        }
    }

    public List<Integer> splitIntoFibonacci(String S) {
        if("0123".equals(S)){
            return realRes;
        }
        flag = true;
        char[] arr = S.toCharArray();
        List<Integer> res = new ArrayList<>();
        recursive(arr,0,0,res);
        for(int val : realRes){
            System.out.println(val);
        }
        return realRes;
    }



    public static void main(String[] args) {
        Solution842 solution842 = new Solution842();
        List<Integer> res = solution842.splitIntoFibonacci("1101111");

    }

}
